package arithmetic.demo11;

import java.util.*;

/**
 * 题目： 字符串_最长公共前缀
 * 方法二： 两两一对比
 */
class Solution {
    public String longestCommonPrefix(String[] strs) {
        int  n = strs.length;
          if(n == 0) return "";

          String tmp = strs[0];

        // 开始遍历一个逐个比较
        for(int i = 1; i < n; i++) {
             tmp = checkSame(tmp, strs[i]);
        }

        //  最终返回结果
        return tmp;


    }

    // 进行两两比较多过程
    private String checkSame(String s1, String s2 ) {
            int i = 0; 
            while(i < s1.length() && i < s2.length() ) {
                if(s1.charAt(i) == s2.charAt(i)) {
                    i++;
                } else {
                    break;
                }
            }


            return s1.substring(0, i);
    }
}


/**
 * 题目： 字符串_最长回文子串
 */

class Solution1 {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ret = new String();

        // 遍历整个字符串， 以该i 为位置为中心
        // 向两边扩展
        for(int i = 0; i < n ; i++) {
            // 获取这个位置的最长回文子串
            String str = CheckKai(s, i);
            ret = ret.length() > str.length() ? ret :  str;
        }

        return ret;

    }

    public String CheckKai(String str, int mid ) {

        // 奇数回文对
        int left   = mid , right = mid;
        while(left >= 0 && right < str.length())  {
            // 相同就往两边走
            if(str.charAt(left) == str.charAt(right)) {
                left--;
                right++;
            } else {
                // 不相同就直接跳出
                break;
            }
        }


        String str1 = str.substring(left + 1, right);

        // 偶数对 的情况
        left   = mid ; right = mid + 1;
        while(left >= 0 && right < str.length())  {
            if(str.charAt(left) == str.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }


        String str2 = str.substring(left + 1,  right);


        // 最更长谁返回结果
        return str1.length() > str2.length() ? str1 : str2;

    }

}


/**
 * 题目： 字符串_二进制求和
 */

class Solution2 {
    public String addBinary(String a, String b) {
        // 先进行逆置
        StringBuilder str1 =new StringBuilder(a),
                str2 = new StringBuilder(b), ret = new StringBuilder();
        str1.reverse(); str2.reverse();

        int i = 0;
        int tmp = 0;
        int n1 = str1.length(), n2 = str2.length();
        while(i < n1 || i  < n2 || tmp != 0) {

            // 遍历第一个字符串
            if(i < str1.length()) {
                tmp += str1.charAt(i) - '0';
            }

            // 遍历第二个字符串
            if(i < str2.length()) {
                tmp += str2.charAt(i) -'0';
            }


            i++;
            // 最终加入结果
            ret.append((char)(tmp % 2 +'0'));

            // 更新结果
            tmp /= 2;

        }



        return ret.reverse().toString();
    }
}


/**
 * 题目： 字符串_字符串相乘
 */

class Solution3 {
    public String multiply(String num1, String num2) {
        // 特殊情况处理一下
        if(num1.charAt(0) == '0' || num2.charAt(0) == '0') return "0";
        int n1 = num1.length(), n2 = num2.length();
        // 存储每一位
        int[] nums = new int[n1+ n2 -1];

        // 进行无进制相加
        for(int i =0; i<n1; i++) {
            for(int j = 0; j<n2; j++) {
                // 存储每一位
                nums[i+j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }

        StringBuilder ret = new StringBuilder();
        // 开始进位相加
        int pos = nums.length - 1 , tmp = 0;
        while(pos >= 0 || tmp != 0) {
            // 加入数据
            if(pos >= 0){
                tmp += nums[pos--];
            }

            // 加入结果
            ret.append((char)(tmp % 10 + '0'));

            // 更新下一位的数值
            tmp /= 10;
        }


        return ret.reverse().toString();
    }
}


/**
 * 题目： 栈_删除字符串中所有相邻的重复项
 */

class Solution4 {
    public String removeDuplicates(String s) {
        Stack<Character> stack  = new Stack<>();

        // 遍历整个数组
        for(int i =0; i<s.length(); i++) {
            // 栈为 空 或者 不相等就加入
            if(stack.isEmpty() || stack.peek() != s.charAt(i)){
                stack.push(s.charAt(i));
            } else {
                stack.pop();
            }
        }

        StringBuilder ret = new StringBuilder();
        Stack<Character>  newStack = new Stack<>();

        // 用一个临时数组来交换顺序
        while(!stack.isEmpty()) {
            newStack.push(stack.pop());
        }


        // 存储结果
        while(!newStack.isEmpty()) {
            ret.append(newStack.pop());
        }


        return ret.toString();
    }
}


/**
 * 题目：栈_比较含退格的字符串
 * 方法一： 字符串方案
 */

class Solution5 {
    public boolean backspaceCompare(String s, String t) {
        // 用两个 字符串来存储
        StringBuilder str1 = new StringBuilder();
        StringBuilder str2 = new StringBuilder();

        // 分别用新字符串来存储区退格后的字符
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 如果为 空 或者不为 # 就加入字符串
            if( ch != '#' ) {
                str1.append(ch);
            } else if(str1.length() != 0) {
                // 否则就删除
                str1.deleteCharAt(str1.length() - 1);
            }
        }


        for(int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            // 如果为 空 或者不为 # 就加入字符串
            if( ch != '#' ) {
                str2.append(ch);
            } else if(str2.length() != 0) {
                // 否则就删除
                str2.deleteCharAt(str2.length() - 1);
            }
        }

        // 如果长度不相等就一定不相同
        if(str1.length() != str2.length()) {
            return false ;
        }


        // 判断是否一一相等
        for(int i = 0 ; i< str2.length() ; i++) {
            if(str1.charAt(i) != str2.charAt(i)) {
                return false;
            }
        }

        return true;
    }
}


/**
 * 方案二： 栈方案
 */

class Solution6 {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();

        // 两边遍历
        for(int i = 0; i<s.length(); i++) {
            char ch = s.charAt(i);
            // 一旦遇到 # 并且栈不为 空就出栈顶
            if(ch == '#' ) {
                if(!stack1.isEmpty()) {
                    stack1.pop();
                }
            } else {
                stack1.push(ch);
            }
        }


        for(int i = 0; i<t.length(); i++) {
            char ch = t.charAt(i);
            // 一旦遇到 # 并且栈不为 空就出栈顶
            if(ch == '#' ) {
                if(!stack2.isEmpty()) {
                    stack2.pop();
                }
            } else {
                stack2.push(ch);
            }
        }

        // 长度不同的情况
        if(stack1.size() != stack2.size()) {
            return false;
        }


        // 出栈进行比较
        while(!stack1.isEmpty()) {
            if(stack1.pop() != stack2.pop()) {
                return false;
            }
        }


        return true;
    }
}


/**
 * 题目： 栈_基本计算器（二）
 */


class Solution7 {
    public int calculate(String s) {
        int n = s.length();
        // 栈记录数值
        Stack<Integer> stack = new Stack<>();
        // char 来记录操作符
        char pas  = '+';


        // 先计算乘除
        for(int i =0; i<n; i++) {

            // 先提取数字
            boolean flg = false;
            int num  = 0;
            while(i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                flg = true;
                num =  ((num * 10) + (s.charAt(i) - '0') );
                i++;
            }

            if(flg) {
                // 如果是加号就直接扔进栈中
                if(pas == '+') {
                    stack.push(num);
                } else if(pas == '-') {
                    stack.push(-num);
                } else if(pas == '*'){
                    int left = stack.pop();
                    stack.push(left * num);
                } else if(pas == '/') {
                    int left = stack.pop();
                    int result = left / num;
                    stack.push(result);
                }
            }

            // 修改符号
            if(i < n) {
                char ch = s.charAt(i);
                if(ch == '+' || ch == '-'|| ch == '*' || ch == '/') {
                    pas = ch;
                }
            }
        }





        int ret = 0;
        // 再计算加减
        while(!stack.isEmpty()) {
            ret += stack.pop();
        }


        return ret;
    }
}

class  Test {
    public static void main(String[] args) {
        String str= "42";
        Solution7 solution7 = new Solution7();
         int sum = solution7.calculate(str);
        System.out.println(sum);
    }
}